package main.二分查找;

/**
 * @author tmh
 * @date 2024/7/24 21:25
 * @description
 */
public class T33搜索旋转排序数组 {
    /**
     * 和T35的思路是一样的
     *
     * @param nums
     * @param target
     * @return
     */
    public int search(int[] nums, int target) {
        int low = 0;
        int high = nums.length;
        int n = nums.length - 1;
        while (low < high) {
            int mid = low + ((high - low) >> 1);
            if (nums[mid] > nums[n]) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        //这个rotationPoint指向的是排序数组的最小值
        //这个第二步，就是来判断这个target在哪个部分，前半部分还是后半部分
        int rotationPoint = high;
        low = 0;
        high = nums.length - 1;
        if (nums[rotationPoint] <= target && target <= nums[high]) {
            low = rotationPoint;
        } else {
            high = rotationPoint - 1;
        }
        //第三步，二分查找自己需要的数值
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
}
